#include<iostream>
#include<math.h>
using namespace std;

class NumericalPerfectionLevel
{
	public:
	int getLevel(long long N)
	{
		int level=0;
		int count=0;
		if(isprime(N)) return 0;
		for(long long i=2; i*i<=N;i++)
		{
			while(N%i==0)
			{
				N/=i;
				count++;
			}
		}
		//There may be a prime larger than sqrt(N) exists.
		if(N!=1) count++;
		while(count/4>0)
		{
			count/=4;
			level++;
		}
		return level;
	}
	private:
	bool isprime(long long K)
	{
		if(K<2)
			return false;
		else if(K==2)
			return true;
		else
		{
			for(long long i=3; i*i<=K;i++)
			{
				if(K%i==0)
					return false;
			}
		}
		return true;
	}
};
